import java.util.Deque;
import java.util.LinkedList;

/**
 * 1124. 表现良好的最长时间段
 * https://leetcode-cn.com/problems/longest-well-performing-interval/
 */
public class Solutions_1124 {
    public static void main(String[] args) {
        int[] hours = {9, 9, 6, 0, 6, 6, 9};
        int result = longestWPI(hours);
        System.out.println(result);
    }

    /**
     * 解题思路：单调栈
     * 单调递减栈
     */
    public static int longestWPI(int[] hours) {
        // 预处理
        for (int i = 0; i < hours.length; i++) {
            if (hours[i] > 8) {
                hours[i] = 1;
            } else {
                hours[i] = -1;
            }
        }
        // 关键：preSum[0] 设置为 0
        int[] preSum = new int[hours.length + 1];
        preSum[0] = 0;
        for (int i = 1; i < preSum.length; i++) {
            preSum[i] = preSum[i - 1] + hours[i - 1];
        }
        Deque<Integer> stack = new LinkedList<>();
        stack.push(preSum[0]);
        for (int i = 1; i < preSum.length; i++) {
            if (preSum[i] < preSum[stack.peek()]) {
                stack.push(i);
            }
        }
        int res = 0;
        for (int i = preSum.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && preSum[i] > preSum[stack.peek()]) {
                res = Math.max(res, i - stack.pop());
            }
        }
        return res;
    }
}
